package com.cn.algorithm01;

/**
 * 归并排序，空间复杂度0(N*logN)
 */
public class Code26_MergeSort {

    // 递归实现排序
    public static void mergeSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        process(arr, 0, arr.length - 1);
    }

    // 递归处理排序
    // 此处无排序，直至递归至两个单数进行比较
    private static void process(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }

        int mid = L + (R - L) / 2;
        //递归处理
        process(arr, L, mid);
        process(arr, mid+1, R);
        merge(arr, L, mid, R);
    }

    // 对排好顺序的两个树进行排序
    private static void merge(int[] arr, int L, int mid, int R) {
        int[] temp = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = mid + 1;
        // p1、p2是左右两个数组的指针，通过对比将小的数依次放入temp数组中，最后将arr数组中覆盖完成排序
        if (p1 <= mid && p2 <= R) {
            temp[i++] = arr[p1++] <= arr[p2++] ? arr[p1++] : arr[p2++];
        }
        //判断越界的进行处理
        if (p1 <= mid) {
            temp[i++] = arr[p1++];
        }
        if (p2 <= R) {
            temp[i++] = arr[p2++];
        }
        // 将排好序的数组覆盖原数组
        for (int x = 0; x < (R - L + 1); x++) {
            arr[L++] = temp[x];
        }

    }
}
